package kaiao.dynamic;

import java.util.Arrays;

public class 完全平方数 {

	public static void main(String[] args) {
		numSquares(12);
	}

	public static int numSquares(int n) {
		// 考虑n+1时与n和n-1的推导关系 有时可能不是n-1和n的关系，主要在于找到上一个重要节点的数据
		// 递归和动态规划本质上的区别是 递归在于入栈入栈出栈出栈 ，动态规划相较于递归有点在于实时计算了过程值

		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		dp[1] = 1;

		for (int i = 2; i < n + 1; i++) {

			// 主要是找到上个对应节点的数据
			for (int j = 1; j * j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
			}
		}

		return dp[n];
 	}
}
